import org.w3c.dom.ls.LSException;

import java.util.*;

public class TreeList {

    class TreeNode {
        public char val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(char val) {
            this.val = val;
        }
    }

    public void leveloder(TreeNode root) {
        if (root == null) {
            return;
        }
        Queue<TreeNode> queue = new LinkedList<>();

        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode p = queue.poll();
            System.out.print(p.val + " ");
            if (p.left != null) {
                queue.offer(p.left);
            }
            if (p.right != null) {
                queue.offer(p.right);
            }
        }
    }
    public int i = 0;

    public TreeNode creatTree(String str) {
        TreeNode root = null;
        if (str.charAt(i) != '#') {

            root = new TreeNode(str.charAt(i));
            i++;
            root.left = creatTree(str);
            root.right = creatTree(str);

        } else {
            i++;
        }
        return root;
    }

    public List<List<Character>> levelOrder(TreeNode root) {
        List<List<Character>> lists = new ArrayList<>();
        if (root == null) {
            return lists;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Character> list = new ArrayList<>();
            while (size != 0) {

                TreeNode t = queue.poll();
                list.add(t.val);
                if (t.left != null) {
                    queue.offer(t.left);
                }
                if (t.right != null) {
                    queue.offer(t.right);
                }
                size--;
            }
            lists.add(list);
        }
        return lists;


    }

    public boolean isComplete(TreeNode root) {
        if (root == null) {
            return true;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode t = queue.poll();
            if (t != null) {
                queue.offer(t.left);
                queue.offer(t.right);
            } else {
                break;
            }

        }
        while (!queue.isEmpty()) {
            TreeNode p = queue.peek();
            if (p != null) {
                return false;
            }
            queue.poll();
        }
        return true;
    }

    public boolean isCompleteTree(TreeNode root) {
        if (root == null) {
            return true;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode t = queue.poll();
            if (t != null) {
                queue.offer(t.left);
                queue.offer(t.right);
            } else {
                break;
            }
        }
        while (!queue.isEmpty()) {
            TreeNode p = queue.peek();
            if (p != null) {
                return false;
            }
            queue.poll();
        }
        return true;
    }

    public List<List<Character>> levelinoder(TreeNode root) {
        List<List<Character>> lists = new ArrayList<>();
        if (root == null) {
            return lists;
        }
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        while (!q.isEmpty()) {
            List<Character> list = new ArrayList<>();
            int size = q.size();
            while (size != 0) {
                TreeNode p = q.poll();
                list.add(p.val);
                if (p.left != null) {
                    q.offer(p.left);
                }
                if (p.right != null) {
                    q.offer(p.right);
                }
                size--;
            }
            lists.add(list);
        }
        return lists;


    }

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return root;
        }
        if (root == p || root == q) {
            return root;
        }

        TreeNode lefttree = lowestCommonAncestor(root.left, p, q);
        TreeNode righttree = lowestCommonAncestor(root.right, p, q);
        if (lefttree != null && righttree != null) {
            return root;
        } else if (lefttree != null) {
            return lefttree;
        } else {
            return righttree;
        }
    }

    private boolean getPath(TreeNode root, TreeNode node, Stack<TreeNode> p) {
        if (root == null) {
            return false;
        }
        p.push(root);
        if (root == node) {
            return true;
        }
        boolean lefttree = getPath(root.left, node, p);
        if (lefttree == true) {
            return true;
        }
        boolean righttree = getPath(root.right, node, p);
        if (righttree == true) {
            return true;
        }
        p.pop();
        return false;
    }

    public TreeNode lowestCommonAncestor1(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }
        Stack<TreeNode> stack1 = new Stack<>();
        Stack<TreeNode> stack2 = new Stack<>();
        getPath(root, p, stack1);
        getPath(root, q, stack2);
        int size1 = stack1.size();
        int size2 = stack2.size();

            if (size1 > size2) {
                int t = size1 - size2;
                while (t != 0) {
                    stack1.pop();
                    t--;
                }
            } else {
                int t = size2 - size1;
                while (t != 0) {
                    stack2.pop();
                    t--;
                }


        }
        while (!stack1.isEmpty() && !stack2.isEmpty()) {
            if (stack1.peek() != stack2.peek()) {
                stack1.pop();
                stack2.pop();
            } else {
                return stack1.peek();
            }

        }
        return null;
    }

}
